package com.mlh.dp.old;

// 给你一个整数数组 prices 和一个整数 k ，其中 prices[i] 是某支给定的股票在第 i 天的价格。
// 设计一个算法来计算你所能获取的最大利润。你最多可以完成 k 笔交易。也就是说，你最多可以买 k 次，卖 k 次。

import java.util.Arrays;

// 输入：k = 2, prices = [2,4,1]
// 输出：2
// 解释：在第 1 天 (股票价格 = 2) 的时候买入，在第 2 天 (股票价格 = 4) 的时候卖出，这笔交易所能获得利润 = 4-2 = 2 。
public class MaxProfit4 {
    public static void main(String[] args) {
        int []prices={2,1,4,5,2,9,7};
        System.out.println(method1(2,prices));
    }

    public static int method1(int k, int[] prices){
        //这边会有2*k个状态  偶数为拥有  奇数为未拥有
        k=2*k;
        int[][]dp=new int[prices.length][k];
        //初始化
        for(int i=0;i<k;i+=2){
            dp[0][i]=-prices[0];
        }
        for(int i=1;i<prices.length;++i){
            for(int j=0;j<k;j++){
                if(j%2==0){//偶数状态定义
                    if(j==0){//0单独定义
                        dp[i][j]=Math.max(-prices[i],dp[i-1][j]);
                    }else{
                        dp[i][j]=Math.max(dp[i-1][j-1]-prices[i],dp[i-1][j]);
                    }
                }else {//奇数状态定义
                    dp[i][j]=Math.max(dp[i-1][j-1]+prices[i],dp[i-1][j]);
                }
            }
        }
        int res=0;
        for(int i=1;i<k;i+=2){
            res=Math.max(dp[prices.length-1][i],res);
        }
        return res;
    }

    //对上面的空间进行优化  将二维数组优化成一维数组
    //优化原因 第i天的所有状态都是根据i-1天推出的
    //还优化了不需要临时变量来记录第i-1的dp[k]  原因在MaxProfirt3中
    //该代码已经被优化了很多  不要试图直接看代码来理解
    //应该先看最初版的代码 然后理解优化原因  进而推导出这样的代码
    public static int method2(int k, int[] prices){
        //这边会有2*k个状态  偶数为拥有  奇数为未拥有
        k=2*k;
        int[]dp=new int[k];
        //初始化
        for(int i=0;i<k;i+=2){
            dp[i]=-prices[0];
        }
        for(int i=1;i<prices.length;++i){
            for(int j=0;j<k;j++){
                if(j%2==0){//偶数状态定义
                    if(j==0){//0单独定义
                        dp[j]=Math.max(-prices[i],dp[j]);
                    }else{
                        dp[j]=Math.max(dp[j-1]-prices[i],dp[j]);
                    }
                }else {//奇数状态定义
                    dp[j]=Math.max(dp[j-1]+prices[i],dp[j]);
                }
            }
        }
        int res=0;
        for(int i=1;i<k;i+=2){
            res=Math.max(dp[i],res);
        }
        return res;
    }

}
